/**
 * 704. 二分查找
 * 34. 排序数组中查找元素第一和最后一个位置
 * 35. 搜索插入位置
 * 69. x的平方根
 * 367. 有效的完全平方数
 * 153. 寻找排序数组中的最小值I
 * 154. 寻找排序数组中的最小值II
 * **/

#include <iostream>
#include <vector>
using std::cout;
using std::endl;
using std::vector;

template <class T>
void print(const T &t)
{
    class T::const_iterator it = t.begin();
    for (; it != t.end(); ++it) {
        cout << *it << " ";
    }
    cout << endl;
}

class Solution
{
  public:
    // 704.
    int search(vector<int> &nums, int target)
    {
        int left = 0, right = nums.size() - 1;
        // 方法一：左闭右闭区间 [left, right]
        // while (left <= right) {
        //     int mid = left + (right - left) / 2;
        //     if (nums[mid] == target) {
        //         return mid;
        //     } else if (nums[mid] < target) {
        //         left = mid + 1;
        //     } else {
        //         right = mid - 1;
        //     }
        // }
        // 方法二：左闭右开区间[left, right)
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] == target) {
                return mid;
            } else if (nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return -1; // not find
    }
    // 35.
    int searchInsert(vector<int> &nums, int target)
    {
        int left = 0, right = nums.size() - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return left;
    }

    // 34.
    vector<int> searchRange(vector<int> &nums, int target)
    {
        int leftIdx = searchInsert(nums, target);
        int rightIdx = searchInsert(nums, target + 1) - 1;
        // 没找到，要么在最左边要么在最右边
        if (leftIdx == nums.size() || nums[leftIdx] != target)
            return {-1, -1};
        return {leftIdx, rightIdx};
    }

    int mySqrt(int x)
    {
        if (x == 0 || x == 1) {
            return x;
        }
        int left = 0, right = x / 2;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if ((long long)mid * mid == x) { // 用除法有除0问题，还是算了
                return mid;
            } else if ((long long)mid * mid < x) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        // 退出循环时left > right
        return right;
    }

    bool isPerfectSquare(int num)
    { // num 正整数
        if (num == 1) {
            return true;
        }
        int left = 0, right = num / 2;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if ((long long)mid * mid == num) {
                return true;
            } else if ((long long)mid * mid < num) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return false;
    }
    // 153./154. 二者的区别是153严格单调递增，154单调非递减
    int findMin(vector<int> &nums)
    {
        // 二分
        int left = 0, right = nums.size() - 1;
        while (left < right) {
            int mid = left + (right - left) / 2;
            // 去右半边
            if (nums[mid] > nums[right]) {
                left = mid + 1;
                // 去左半边
            } else if (nums[mid] > nums[right]) {
                right = mid;
                // nums[mid]==nums[right]时无法决定去哪个半区间
                // 但是不要慌，左闭右开区间的二分查找确定了left<right,
                // mid也一定小于right，因此可以忽略右端点
            } else {
                --right;
            }
        }
        return nums[left];
    }
};

Solution solve = Solution();

void test704()
{
    vector<int> nums = {-1, 0, 3, 5, 9, 12};
    int target = 2;
    cout << solve.search(nums, target) << endl;
}
void test34()
{
    vector<int> nums = {5, 7, 7, 8, 8, 10};
    int target = 7;
    print(solve.searchRange(nums, target));
}

void test35()
{ // 见34.
}

void test69()
{
    cout << solve.mySqrt(4) << endl;     // 2
    cout << solve.mySqrt(8) << endl;     // 2
    cout << solve.mySqrt(16) << endl;    // 4
    cout << solve.mySqrt(32) << endl;    // 5
    cout << solve.mySqrt(65536) << endl; // 256
}

void test367()
{
    cout << solve.isPerfectSquare(4) << endl;     // 1
    cout << solve.isPerfectSquare(8) << endl;     // 0
    cout << solve.isPerfectSquare(16) << endl;    // 1
    cout << solve.isPerfectSquare(32) << endl;    // 0
    cout << solve.isPerfectSquare(65536) << endl; // 1
}

void test153_154()
{
    vector<int> nums153 = {4, 5, 6, 7, 0, 1, 2};
    vector<int> nums154 = {4, 4, 4, 5, 0, 1, 1};
    cout << solve.findMin(nums154) << endl;
}

int main()
{
    // test704();
    // test34();
    // test35();
    // test69();
    // test367();
    test153_154();

    return 0;
}